Computers, broadly speaking, are electronic machines capable of storing and manipulating information, often called data, to useful ends. Frequently, a number of computers are connected together in such a way that they are able to send data to each other. A collection of computers so connected is often called a network, and the connector between two network nodes is referred to as a link. One type of computer network is called a LAN (local area network), and may be found, for example, in the offices of a small business or educational institution. A number of LANs or other networks may also be brought into communication with each other. As might be expected, a system of rules or set procedures must be put in place so that the computers and networks can communicate with each other effectively. Such a system of rules and procedures is often called a protocol, and several have been developed for communications involving computer networks.
A widely accepted set of protocols for LAN communications has been developed under the auspices of the IEEE (Institute of Electrical and Electronics Engineers). A standard generally referred to as IEEE 802, for example, covers general network architecture, IEEE 802.1 deals with bridging and management, and IEEE 802.3 is the Ethernet protocol. An Ethernet LAN is generally one that handles traffic, that is, the flow of data from one computer to one or more other, using a system of collision detection and avoidance. (A ‘collision’ occurs when two or more computers attempt to send data over the same link at the same time.) These standards are regularly reviewed and updated as necessary to improve networks operations and account for developments in technology.
In a typical Ethernet network, data sent from one computer to another, or from one network to another, is not transmitted all at once or continuously, but is instead broken up into discrete ‘frames’. Using frames of data better allows the network computers to take turns sending data. The frames may vary in length, but each frame includes sufficient address information (in addition to the actual data) so it may be routed to its desired destination or destinations. Routing is necessary because every computer is not connected directly to every other. Instead, computers and networks are connected to intermediary devices that receive data, determine its destination address, and then route it accordingly. One such intermediary device is referred to as a bridge. A bridge is a type of software switch resident on a network component. A frame of data may be routed through many bridges on its way from source to destination.
FIG. 15 is a simplified schematic diagram illustrating the bridges of an exemplary network 10, in which embodiments of the present invention may be advantageously implemented. The network 10 may have many components, but for clarity only the bridges themselves are shown. Individual components such as computers and sub-networks may be connected to one of the bridges. In the embodiment of FIG. 15, there are nine bridges, numbered 1 through 9, although the present invention is also suitable for implementation in larger or smaller networks. Each of these bridges 1 through 9 is connected by a link to one or more other bridges. In FIG. 15 the links are numbered according to the bridges it connects, for example link 24 connects bridge 2 directly with bridge 4. A path includes all of the links from one bridge to another, for example one path from bridge 1 to bridge 9 includes links 13, 38, and 89. As should be apparent, there may be more than one path between any two bridges.
When a bridge receives a data frame from, for example, a network computer or another bridge, it examines the address information and forwards the frame accordingly. Data may have to pass through several bridges from its source to destination. Without some governing protocol, however, it is possible that frames of data might inadvertently be sent from bridge to bridge, eventually looping back to a previously-visited bridge from which they are re-sent back into the same loop. As should be apparent, this is not a desirable phenomenon and techniques have evolved for avoiding this looping problem.
One technique to avoid looping would be to use a fixed-configuration network and always route frames intended for a particular destination by the same route. Most networks are subject to change, however, and occasionally encounter break downs or congestion in components and links. A static routing system is therefore not the best solution. In a more successful solution, a ‘spanning tree’ is calculated periodically according to a spanning tree protocol (STP). The spanning tree provides path definitions for the network as it exists at the time of the tree calculation. In the event of a failure or other event, the tree can be recalculated to adjust to the new conditions.
Calculation of a spanning tree preferably involves not only designating a path from each source to each destination, but determining the best pathways for each case so that network communications are accomplished in an efficient manner. IEEE standards, for example, often use distance vector mechanisms to determine an active topology for the network, the active topology referring to the tree of data forwarding paths that will be used to route data traffic. This distance vector technique is well known and will not be discussed here in detail, except to note that the active topology is configured in a distributed manner, and so no bridge in the network is aware of the data distribution scheme in its entirety. It is therefore possible, or even likely, that the topology is not optimal. The distance vector approach is also less efficient at fault handling, that is at recovering from a failure occurring somewhere in the network.
A better solution may be to use a link state spanning tree calculation by applying the core functionality of IP (Internet protocol) using routing protocols such as OSPF (open shortest path first) and IS-IS (intermediate system to intermediate system). IP protocols are typically developed and disseminated by the IETF (Internet engineering task force). In general, the link state approach facilitates application of traffic engineering and allows the active topology to be optimized. Directly implementing IP routing protocols, however, would mean each bridge would have to set up its own forwarding tables. This is not a detriment in and of itself, but it may produce long unavailable periods resulting in at least transient loops. Another complication is that Ethernet frames do not include a TTL (time to live) field (as does an IP packet) so transient loops may be problematic when changes in active topology are occurring. Of course, bridges that notice the topology is changing could simply stop forwarding data frames until a new topology is calculated, but this procedure slows down the recovery significantly.
There is therefore a need in the art for a manner in which to implement a link state approach to spanning tree calculation that retains the advantages of link state protocols, but mitigates or eliminates the problems they have, especially those associated with an occasionally changing active topology. The present invention provides just such a solution.